In general, operation processing speed of a processor or a hardware engine is faster than data providing speed of a main memory constituted by a DRAM or the like. A cache memory is used to make up for the speed difference. The cache memory is a memory constituted by an SRAM or the like that operates at a higher speed than a main memory, and it temporarily stores data of the main memory. A processor and the like can perform high-speed processing by accessing data stored not in the main memory but in the cache memory. The cache memory has a smaller capacity in comparison with the main memory, and it stores only a part of data of the main memory in unit of a predetermined block size.
The data stored in the main memory is, for example, a matrix. When a processor or the like accesses the matrix, a part of the matrix is copied to the cache memory. A matrix is classified as a sparse matrix in which most of its elements have the same value (for example, zero) or a dense matrix which is constituted by a variety of different elements. In general, a matrix used for scientific and technical calculation is a sparse matrix in many cases.
Conventionally, when data stored in a main memory is a sparse matrix, all data included in a specified part of the matrix is copied to a cache though most of the data is the same data. That is, even when the data is a sparse matrix, the cache memory is required to have a storage capacity corresponding to an amount of data used by a processor or the like.
The cache memory, however, is expensive, and there is a great demand for downsizing of apparatuses. Therefore, there is a demand for reducing storage capacity as far as possible.